{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count Square Sum Triples"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math #enumeration"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学 #枚举"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countTriples"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #统计平方和三元组的数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>一个 <strong>平方和三元组</strong> <code>(a,b,c)</code> 指的是满足 <code>a<sup>2</sup> + b<sup>2</sup> = c<sup>2</sup></code> 的 <strong>整数 </strong>三元组 <code>a</code>，<code>b</code> 和 <code>c</code> 。</p>\n",
    "\n",
    "<p>给你一个整数 <code>n</code> ，请你返回满足<em> </em><code>1 &lt;= a, b, c &lt;= n</code> 的 <strong>平方和三元组</strong> 的数目。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>n = 5\n",
    "<b>输出：</b>2\n",
    "<b>解释：</b>平方和三元组为 (3,4,5) 和 (4,3,5) 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>n = 10\n",
    "<b>输出：</b>4\n",
    "<b>解释：</b>平方和三元组为 (3,4,5)，(4,3,5)，(6,8,10) 和 (8,6,10) 。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 250</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-square-sum-triples](https://leetcode.cn/problems/count-square-sum-triples/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-square-sum-triples](https://leetcode.cn/problems/count-square-sum-triples/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['5', '10']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriples(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(i + 1, n + 1):\n",
    "                for k in range(j + 1, n + 1):\n",
    "                    if i*i + j*j == k*k:\n",
    "                        ans += 2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def countTriples(self, n: int) -> int:\n",
    "        cnt=0\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(i+1,n+1):\n",
    "                if math.sqrt(i**2+j**2)%1==0 and math.sqrt(i**2+j**2)<=n:\n",
    "                    cnt+=1\n",
    "        return cnt*2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriples(self, n: int) -> int:\n",
    "        temp={x**2 for x in range(1,n+1)}\n",
    "        self.ans=0\n",
    "        def dfs(nums,res):\n",
    "            if len(res)==2:\n",
    "                if res[0]**2+res[1]**2 in temp:\n",
    "                    self.ans+=1\n",
    "                return\n",
    "            for i in range(len(nums)):\n",
    "                dfs(nums[:i]+nums[i+1:],res+[nums[i]])\n",
    "        dfs(list(range(1,n+1)),[])\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriples(self, n: int) -> int:\n",
    "        count = 0\n",
    "        for i in range(1 , n + 1):\n",
    "            for j in range(1 , n + 1):\n",
    "                k = int(sqrt(i ** 2 + j ** 2 + 1))\n",
    "                if k <= n and k ** 2 == i ** 2 + j ** 2:\n",
    "                    count += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import sqrt\n",
    "\n",
    "class Solution:\n",
    "    def countTriples(self, n: int) -> int:\n",
    "        res = 0\n",
    "        # 枚举 a 与 b\n",
    "        for a in range(1, n + 1):\n",
    "            for b in range(1, n + 1):\n",
    "                # 判断是否符合要求\n",
    "                c = int(sqrt(a ** 2 + b ** 2 + 1))\n",
    "                if c <= n and c ** 2 == a ** 2 + b ** 2:\n",
    "                    res += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriples(self, n: int) -> int:\n",
    "        l = []\n",
    "        ans = 0\n",
    "        for i in range(1, n + 1):\n",
    "            l.append(i * i)\n",
    "        for a in l:\n",
    "            for b in l:\n",
    "                if (a + b) in l:\n",
    "                    ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriples(self, n: int) -> int:\n",
    "        res = 0\n",
    "        for a in range(1, n):\n",
    "            for b in range(a + 1, n):\n",
    "                for c in range(b + 1, n + 1):\n",
    "                    if a*a + b*b == c*c:\n",
    "                        res += 2\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriples(self, n: int) -> int:\n",
    "        count = 0\n",
    "        for i in range(1, n - 1):\n",
    "            for j in range(i + 1, n):\n",
    "                for x in range(j + 1, n + 1):\n",
    "                    if i * i + j * j == x * x:\n",
    "                        count += 1\n",
    "        return count * 2\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriples(self, n: int) -> int:\n",
    "        temp = dict()\n",
    "        for i in range(1,n + 1):\n",
    "            temp[i ** 2] = 1 #用字典存平方，减少一重循环\n",
    "        count = 0\n",
    "        for i in range(1,n - 1):\n",
    "            for j in range(i + 1,n):\n",
    "                if i ** 2 + j ** 2 in temp:\n",
    "                    count += 1\n",
    "        return count*2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriples(self, n: int) -> int:\n",
    "\n",
    "        pow_set = set()\n",
    "        for c in range(1, n + 1):\n",
    "            pow_set.add(c * c)\n",
    "        \n",
    "        res = 0\n",
    "        for a in range(1, n + 1):\n",
    "            for b in range(a + 1, n + 1):\n",
    "                if a * a + b * b in pow_set:\n",
    "                    res += 2\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriples(self, n: int) -> int:\n",
    "        count = 0\n",
    "        for a in range(1, n):\n",
    "            for b in range(a + 1, n):\n",
    "                for c in range(b + 1, n + 1):\n",
    "                    if a*a + b*b == c*c:\n",
    "                        count += 2\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriples(self, n: int) -> int:\n",
    "        from math import sqrt\n",
    "        count=0\n",
    "        for i in range(1,n):\n",
    "            for j in range(i+1,n):\n",
    "                k=sqrt(i**2+j**2)\n",
    "                if k%1==0 and int(k)<=n:\n",
    "                    count+=1\n",
    "        return 2*count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriples(self, n: int) -> int:\n",
    "        res = 0\n",
    "        for a in range(1, n+1):\n",
    "            for b in range(1, n+1):\n",
    "                c = int(sqrt(a**2 + b**2))\n",
    "                if c <= n and c**2 == a**2 + b**2:\n",
    "                    res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriples(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        s = [i**2  for i in range(n+1)]\n",
    "        for a in range(1,n):\n",
    "            for b in range(a+1,n):\n",
    "                if a**2 + b**2 in s:\n",
    "                    ans += 2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriples(self, n: int) -> int:\n",
    "        d=0\n",
    "        for a in range(1,n+1):\n",
    "            for b in range (1,n+1):\n",
    "                c=int(sqrt(a**2+b**2+1))\n",
    "                if c<=n and c*c==a*a+b**2 :\n",
    "                        d+=1\n",
    "        return d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriples(self, n: int) -> int:\n",
    "\n",
    "        dataList = []\n",
    "        for i in range(1, n+1):\n",
    "            dataList.append(i * i)\n",
    "\n",
    "        total = 0\n",
    "        for i in range(2, len(dataList)):\n",
    "             for j in range(i):\n",
    "                 if ((dataList[i] - dataList[j]) in dataList[:i] and (dataList[i] - dataList[j]) != dataList[j]):\n",
    "                     total += 1\n",
    "        return total\n",
    "             "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriples(self, n: int) -> int:\n",
    "        res = 0\n",
    "        for i in range(1,n):\n",
    "            for j in range(i+1,n):\n",
    "                c = (i ** 2 + j ** 2) ** 0.5\n",
    "                if c % 1 == 0 and c <= n:\n",
    "                    res+=1\n",
    "        return res*2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriples(self, n: int) -> int:\n",
    "        d = 0\n",
    "        for a in range(1,n-1):\n",
    "            for b in range(a+1,n):\n",
    "                k = math.sqrt(a*a+b*b)\n",
    "                if int(k)==k and k<=n:                  \n",
    "                        d+=1\n",
    "        t = 2*d                \n",
    "        return t                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriples(self, n: int) -> int:\n",
    "        cnt = 0\n",
    "        res = set([i*i for i in range(1,n+1)])\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(1,i):\n",
    "                if i*i + j*j in res:\n",
    "                    cnt += 2\n",
    "        \n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriples(self, n: int) -> int:\n",
    "        res = 0\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(i+1,n+1):\n",
    "                k = math.sqrt(i*i + j*j)\n",
    "                if int(k) == k and k <= n:\n",
    "                    res += 2\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriples(self, n: int) -> int:\n",
    "        import math\n",
    "        num = 0\n",
    "        for i in range(1, n):\n",
    "            for j in range(1, n):\n",
    "                k=i**2+j**2\n",
    "                if math.sqrt(k).is_integer() and k<=n**2:\n",
    "                    num += 1\n",
    "        return num\n",
    "\n",
    "solution=Solution()\n",
    "print(solution.countTriples(5))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import sqrt\n",
    "\n",
    "class Solution:\n",
    "    def countTriples(self, n: int) -> int:\n",
    "        res = 0\n",
    "        # 枚举 a 与 b\n",
    "        for a in range(1, n + 1):\n",
    "            for b in range(1, n + 1):\n",
    "                # 判断是否符合要求\n",
    "                c = int(sqrt(a ** 2 + b ** 2 ))\n",
    "                if c <= n and c ** 2 == a ** 2 + b ** 2:\n",
    "                    res += 1\n",
    "        return res\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriples(self, n: int) -> int:\n",
    "        cnt = 0\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(i+1, n+1):\n",
    "                k = math.sqrt(i * i + j * j)\n",
    "                if int(k) == k and k <= n:\n",
    "                    cnt += 2 \n",
    "        return cnt\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countTriples(self, n: int) -> int:\n",
    "        ans=set()\n",
    "        for c in range(1,n+1):\n",
    "            i,j=1,c-1\n",
    "            while i<j:\n",
    "                s=i*i+j*j\n",
    "                if s>c*c:\n",
    "                    j-=1\n",
    "                elif s<c*c:\n",
    "                    i+=1\n",
    "                else:\n",
    "                    ans.add((i,j,c))\n",
    "                    ans.add((j,i,c))\n",
    "                    i+=1\n",
    "        return len(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriples(self, n: int) -> int:\n",
    "        res=[]\n",
    "        r=[x**2 for x in range(n+1)]\n",
    "        for i in range(1,len(r)-1):\n",
    "            for j in range(i+1,len(r)):\n",
    "                if r[i]+r[j] in r:\n",
    "                    res.append([i,j,r.index(r[i]+r[j])])\n",
    "                    res.append([j,i,r.index(r[i]+r[j])])\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriples(self, n: int) -> int:\n",
    "        \"\"\"\n",
    "        枚举\n",
    "        \"\"\"\n",
    "        cnt = 0\n",
    "        for a in range(1,n+1):\n",
    "            for b in range(1, n+1):\n",
    "                c = int(sqrt(a*a + b*b))\n",
    "                if c<=n and c*c == a*a + b*b:\n",
    "                    cnt += 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriples(self, n: int) -> int:\n",
    "        res = 0\n",
    "        # 枚举 a 与 b\n",
    "        for a in range(1, n + 1):\n",
    "            for b in range(1, n + 1):\n",
    "                # 判断是否符合要求\n",
    "                c = int(sqrt(a ** 2 + b ** 2 + 1))\n",
    "                if c <= n and c ** 2 == a ** 2 + b ** 2:\n",
    "                    res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriples(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        li = [pow(i, 2) for i in range(1, n + 1)]\n",
    "        for i in range(n):\n",
    "            for x in range(i):\n",
    "                if li[i] - li[x] in li:\n",
    "                    ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriples(self, n: int) -> int:\n",
    "\n",
    "        pow_set = set()\n",
    "        for c in range(1, n + 1):\n",
    "            pow_set.add(c * c)\n",
    "        \n",
    "        res = 0\n",
    "        for a in range(1, n + 1):\n",
    "            for b in range(a + 1, n + 1):\n",
    "                if a * a + b * b in pow_set:\n",
    "                    res += 2\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriples(self, n: int) -> int:\n",
    "        ares = 0\n",
    "        res = 0\n",
    "        # 枚举 a 与 b\n",
    "        for a in range(1, n + 1):\n",
    "            for b in range(1, n + 1):\n",
    "                # 判断是否符合要求\n",
    "                c = int(sqrt(a ** 2 + b ** 2 + 1))\n",
    "                if c <= n and c ** 2 == a ** 2 + b ** 2:\n",
    "                    res += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def countTriples(self, n: int) -> int:\n",
    "        res = 0\n",
    "        for i in range(3,n+1):\n",
    "            for j in range(2,i):\n",
    "                tmp = int(math.sqrt(i**2-j**2+1))\n",
    "                if tmp**2 + j**2 == i**2:\n",
    "                    res+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriples(self, n: int) -> int:\n",
    "        cnt = 0\n",
    "        res = set([i*i for i in range(1,n+1)])\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(1,i):\n",
    "                if i*i + j*j in res:\n",
    "                    cnt += 2\n",
    "        \n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriples(self, n: int) -> int:\n",
    "        st = set(i * i for i in range(1, n + 1))\n",
    "        ans = 0\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(i + 1, n + 1):\n",
    "                if i*i + j*j in st:\n",
    "                    ans += 2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriples(self, n: int) -> int:\n",
    "      arr = [i*i for i in range(1, n+1)]\n",
    "      # print(arr)\n",
    "      temp = set(arr)\n",
    "      # print(temp)\n",
    "      res = 0\n",
    "      for i in range(n):\n",
    "        for j in range(i+1, n):\n",
    "          if arr[i] + arr[j] in temp:\n",
    "            res += 2\n",
    "      return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriples(self, n: int) -> int:\n",
    "        res  =0 \n",
    "        for a in range(1,n+1):\n",
    "            for b in range(1,n+1):\n",
    "                c= int(sqrt(a**2+b**2+1))\n",
    "                if c <= n and c**2 == a**2+b**2:\n",
    "                    res +=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import sqrt\n",
    "class Solution:\n",
    "\n",
    "    def countTriples(self, n: int) -> int:\n",
    "        count = 0\n",
    "        for a in range(1, n):\n",
    "            for b in range(a + 1, n):\n",
    "                c = int(sqrt(a**2 + b**2 + 1))\n",
    "                if c <= n and c**2 == a**2 + b**2:\n",
    "                    count+=2\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriples(self, n: int) -> int:\n",
    "        ans=[]\n",
    "        for c in range(1,n+1):\n",
    "            i,j=1,c-1\n",
    "            while i<j:\n",
    "                s=i*i+j*j\n",
    "                if s>c*c:\n",
    "                    j-=1\n",
    "                elif s<c*c:\n",
    "                    i+=1\n",
    "                else:\n",
    "                    ans.append((i,j,c))\n",
    "                    i+=1\n",
    "        return len(ans)*2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriples(self, n: int) -> int:\n",
    "        res = 0\n",
    "        for a in range(1,n+1):\n",
    "            for b in range(1,n+1):\n",
    "                c= int(sqrt(a**2+b**2+1))\n",
    "                if c<=n and c**2 == a**2+b**2:\n",
    "                    res+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import sqrt\n",
    "\n",
    "class Solution:\n",
    "    def countTriples(self, n: int) -> int:\n",
    "        res = 0\n",
    "        # 枚举 a 与 b\n",
    "        for a in range(1, n + 1):\n",
    "            for b in range(1, n + 1):\n",
    "                # 判断是否符合要求\n",
    "                c = int(sqrt(a ** 2 + b ** 2 + 1))\n",
    "                if c <= n and c ** 2 == a ** 2 + b ** 2:\n",
    "                    res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriples(self, n: int) -> int:\n",
    "        d = {5: 2, 10: 2, 13: 2, 15: 2, 17: 2, 20: 2, 25: 4, 26: 2, 29: 2, 30: 2, 34: 2, 35: 2, 37: 2, 39: 2, 40: 2, 41: 2, 45: 2, 50: 4, 51: 2, 52: 2, 53: 2, 55: 2, 58: 2, 60: 2, 61: 2, 65: 8, 68: 2, 70: 2, 73: 2, 74: 2, 75: 4, 78: 2, 80: 2, 82: 2, 85: 8, 87: 2, 89: 2, 90: 2, 91: 2, 95: 2, 97: 2, 100: 4, 101: 2, 102: 2, 104: 2, 105: 2, 106: 2, 109: 2, 110: 2, 111: 2, 113: 2, 115: 2, 116: 2, 117: 2, 119: 2, 120: 2, 122: 2, 123: 2, 125: 6, 130: 8, 135: 2, 136: 2, 137: 2, 140: 2, 143: 2, 145: 8, 146: 2, 148: 2, 149: 2, 150: 4, 153: 2, 155: 2, 156: 2, 157: 2, 159: 2, 160: 2, 164: 2, 165: 2, 169: 4, 170: 8, 173: 2, 174: 2, 175: 4, 178: 2, 180: 2, 181: 2, 182: 2, 183: 2, 185: 8, 187: 2, 190: 2, 193: 2, 194: 2, 195: 8, 197: 2, 200: 4, 202: 2, 203: 2, 204: 2, 205: 8, 208: 2, 210: 2, 212: 2, 215: 2, 218: 2, 219: 2, 220: 2, 221: 8, 222: 2, 225: 4, 226: 2, 229: 2, 230: 2, 232: 2, 233: 2, 234: 2, 235: 2, 238: 2, 240: 2, 241: 2, 244: 2, 245: 2, 246: 2, 247: 2, 250: 6}\n",
    "        ans = 0\n",
    "        for i in range(1, n+1):\n",
    "            if i in d:\n",
    "                ans+=d[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriples(self, n: int) -> int:\n",
    "        sum=0\n",
    "        for i in range(1,n+1):\n",
    "            for k in range(1,n+1):\n",
    "                c = int(sqrt(i*i+k*k+1))\n",
    "                if c <= n and  c*c==i*i+k*k:\n",
    "                    sum+=1\n",
    "        return sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriples(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        for i in range(1, n-1):\n",
    "            for j in range(i, n):\n",
    "                k = math.sqrt(i**2 + j**2)\n",
    "                if int(k) == k and k<=n:\n",
    "                    ans += 2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import sqrt\n",
    "\n",
    "class Solution:\n",
    "    def countTriples(self, n: int) -> int:\n",
    "        res = 0\n",
    "        # 枚举 a 与 b\n",
    "        for a in range(1, n + 1):\n",
    "            for b in range(1, n + 1):\n",
    "                # 判断是否符合要求\n",
    "                c = int(sqrt(a ** 2 + b ** 2 + 1))\n",
    "                if c <= n and c ** 2 == a ** 2 + b ** 2:\n",
    "                    res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def countTriples(self, n: int) -> int:\r\n",
    "        c2 = set()\r\n",
    "        re = 0\r\n",
    "        for c in range(1,n+1):\r\n",
    "            c2.add(c*c)\r\n",
    "        for a in range(1,n+1):\r\n",
    "            for b in range(a+1,n+1):\r\n",
    "                if (a*a + b*b) in c2:\r\n",
    "                    re +=2\r\n",
    "        return re\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriples(self, n: int) -> int:\n",
    "        temp = dict()\n",
    "        for i in range(1,n + 1):\n",
    "            temp[i ** 2] = 1\n",
    "        count = 0\n",
    "        for i in range(1, n - 1):\n",
    "            par = pow(i, 2)\n",
    "            for j in range(i + 1, n):\n",
    "                if par + j ** 2 in temp:\n",
    "                    count += 1\n",
    "        return count * 2\n",
    "\n",
    "# Python：用字典存储平方数的时间效率要高很多！"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def countTriples(self, n: int) -> int:\n",
    "    ans = set()\n",
    "    for c in range(1, n+1):\n",
    "      i, j = 1, c-1\n",
    "      while i < j:\n",
    "        s1 = i*i + j*j\n",
    "        s2 = c*c\n",
    "        if s1 > s2:\n",
    "          j -= 1\n",
    "        elif s1 < s2:\n",
    "          i += 1\n",
    "        else:\n",
    "          ans.add((i ,j, c))\n",
    "          ans.add((j ,i, c))\n",
    "          i += 1\n",
    "    return len(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriples(self, n: int) -> int:\n",
    "        cnt = 0\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(i+1,n+1):\n",
    "                for k in range(j+1,n+1):\n",
    "                    if i*i + j*j == k*k:\n",
    "                        cnt += 2\n",
    "        \n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriples(self, n: int) -> int:\n",
    "        d=0\n",
    "        for a in range(1,n+1):\n",
    "            for b in range (1,n+1):\n",
    "                c=int(sqrt(a**2+b**2))\n",
    "                if c<=n and c*c==a*a+b**2 :\n",
    "                        d+=1\n",
    "        return d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriples(self, n: int) -> int:\n",
    "        i=0\n",
    "        for c in range(1,n+1):\n",
    "            for b in range(1,c):\n",
    "                for a in range(1,b):\n",
    "                    if a*a+b*b==c*c:\n",
    "                        i+=2\n",
    "        return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriples(self, n: int) -> int:\n",
    "        start=1\n",
    "        numberSum=0\n",
    "        for i in range(start,n+1):\n",
    "            for j in range(i+1,n+1):\n",
    "                for k in range(j+1,n+1):\n",
    "                    \n",
    "                    if i*i+j*j<k*k:\n",
    "                        break\n",
    "                    elif i*i+j*j==k*k:\n",
    "                        numberSum+=1\n",
    "        return numberSum*2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriples(self, n: int) -> int:\n",
    "        count = 0\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(i + 1, n + 1):\n",
    "                k2 = i ** 2 + j ** 2\n",
    "                k = int(k2 ** 0.5)\n",
    "                if k <= n and k ** 2 == k2:\n",
    "                    count += 1\n",
    "        return count * 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def countTriples(self, n: int) -> int:\n",
    "#         ans = 0\n",
    "#         for i in range(1, n-1):\n",
    "#             for j in range(i, n):\n",
    "#                 k = math.sqrt(i**2 + j**2)\n",
    "#                 if int(k) == k and k<=n:\n",
    "#                     ans += 2\n",
    "#         return ans\n",
    "class Solution:\n",
    "    def countTriples(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        squares = set(i ** 2 for i in range(1, n + 1))\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, i):\n",
    "                if i * i + j * j in squares:\n",
    "                    ans += 2\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriples(self, n: int) -> int:\n",
    "        res = 0\n",
    "        for i in range(1,n + 1):\n",
    "            for j in range(1,i):\n",
    "                k = (i * i - j * j) ** 0.5\n",
    "                if k < j:\n",
    "                    break\n",
    "                if int(k) == k:\n",
    "                    res += 2\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriples(self, n: int) -> int:\n",
    "        count = 0\n",
    "        for a in range(1, n+1):\n",
    "            for b in range(1, n+1):\n",
    "                # 防止浮点数造成的误差，并且两个相邻的完全平方正数之间的距离一定大于1\n",
    "                c = int(sqrt(a * a + b * b + 1))\n",
    "                if c <= n and a * a + b * b == c * c:\n",
    "                    count += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriples(self, n: int) -> int:\n",
    "        record = 0\n",
    "        for i in range(1, floor(n/(2**0.5))+1):\n",
    "            for j in range(i, floor(sqrt(n**2-i**2)) + 1):\n",
    "                if sqrt(i**2 + j**2) % 1 == 0:\n",
    "                    record += 1\n",
    "        return record*2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriples(self, n: int) -> int:\n",
    "        res=0\n",
    "        for a in range(1,n):\n",
    "            for b in range(a,n):\n",
    "                su=a*a+b*b\n",
    "                tmp=math.sqrt(su)\n",
    "                if tmp<=n and tmp%1==0:\n",
    "                    res=res+2 if a!=b else res+1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriples(self, n: int) -> int:\n",
    "        count=0\n",
    "        for a in range(1,n+1):\n",
    "            for b in range(a,n+1):\n",
    "                c=(a*a+b*b)**0.5\n",
    "                if int(c)==c and c<=n:\n",
    "                        count+=2\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import sqrt\n",
    "\n",
    "class Solution:\n",
    "    def countTriples(self, n: int) -> int:\n",
    "        res = 0\n",
    "        for a in range(1, n + 1):\n",
    "            for b in range(1, n + 1):\n",
    "                c = int(sqrt(a ** 2 + b ** 2 + 1))\n",
    "                if c <= n and c ** 2 == a ** 2 + b ** 2:\n",
    "                    res += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countTriples(self, n: int) -> int:\n",
    "        s=[5, 10, 13, 15, 17, 20, 25, 25, 26, 29, 30, 34, 35, 37, 39, 40, 41, 45, 50, 50, 51, 52, 53, 55, 58, 60, 61, 65, 65, 65, 65, 68, 70, 73, 74, 75, 75, 78, 80, 82, 85, 85, 85, 85, 87, 89, 90, 91, 95, 97, 100, 100, 101, 102, 104, 105, 106, 109, 110, 111, 113, 115, 116, 117, 119, 120, 122, 123, 125, 125, 125, 130, 130, 130, 130, 135, 136, 137, 140, 143, 145, 145, 145, 145, 146, 148, 149, 150, 150, 153, 155, 156, 157, 159, 160, 164, 165, 169, 169, 170, 170, 170, 170, 173, 174, 175, 175, 178, 180, 181, 182, 183, 185, 185, 185, 185, 187, 190, 193, 194, 195, 195, 195, 195, 197, 200, 200, 202, 203, 204, 205, 205, 205, 205, 208, 210, 212, 215, 218, 219, 220, 221, 221, 221, 221, 222, 225, 225, 226, 229, 230, 232, 233, 234, 235, 238, 240, 241, 244, 245, 246, 247, 250, 250, 250,255]\n",
    "       \n",
    "        for i in range(n+1):\n",
    "            if s[i]>n:\n",
    "                return i*2\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "\n",
    "class Solution:\n",
    "    def countTriples(self, n: int) -> int:\n",
    "        count = 0  # 初始化三元组数量为 0\n",
    "        \n",
    "        for a in range(1, n + 1):  # 遍历 a\n",
    "            for b in range(a, n + 1):  # 遍历 b\n",
    "                c_squared = a * a + b * b  # 计算 a^2 + b^2\n",
    "                \n",
    "                # 检查 c_squared 是否是一个完全平方数且 c <= n\n",
    "                c = int(math.sqrt(c_squared))\n",
    "                if c * c == c_squared and c <= n:\n",
    "                    count += 1 if a == b else 2  # 如果 a = b，只增加一个三元组，否则增加两个（a, b, c）和（b, a, c）\n",
    "\n",
    "        return count  # 返回三元组数量\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriples(self, n: int) -> int:\n",
    "        cnt = 0\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(i+1, n+1):\n",
    "                k = sqrt(i*i + j*j)\n",
    "                if int(k) == k and k <= n:\n",
    "                    cnt += 2\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriples(self, n: int) -> int:\n",
    "        res = 0\n",
    "        for i in range(1,n):\n",
    "            for j in range(i+1,n):\n",
    "                if int(math.sqrt(i**2+j**2))**2 == i**2+j**2:\n",
    "                    print(i)\n",
    "                    if int(math.sqrt(i**2+j**2)) <= n:\n",
    "                        res += 2\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import sqrt\n",
    "\n",
    "class Solution:\n",
    "    def countTriples(self, n: int) -> int:\n",
    "        res = 0\n",
    "        # 枚举 a 与 b\n",
    "        for a in range(1, n + 1):\n",
    "            for b in range(1, n + 1):\n",
    "                # 判断是否符合要求\n",
    "                c = int(sqrt(a ** 2 + b ** 2 + 1))\n",
    "                if c <= n and c ** 2 == a ** 2 + b ** 2:\n",
    "                    res += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriples(self, n: int) -> int:\n",
    "\n",
    "        # 穷举   combinations\n",
    "        # def check(t: tuple):\n",
    "        #     # 生成元组是已排好序，x<y<z,所以直接判断x**2+y**2 == z**2\n",
    "        #     if t[0]**2+t[1]**2 == t[2]**2:\n",
    "        #         return True\n",
    "        #     else:\n",
    "        #         return False\n",
    "\n",
    "        # from itertools import combinations \n",
    "        # x = list(combinations([i for i in range(1, n+1)], 3))\n",
    "        # res = 0\n",
    "        # for t in x:\n",
    "        #     # print(t)\n",
    "        #     if check(t):\n",
    "        #         res += 1\n",
    "        # return res*2\n",
    "\n",
    "\n",
    "        # 官解 也是穷举啊！！！\n",
    "        # res = 0\n",
    "        # # 枚举 a 与 b\n",
    "        # for a in range(1, n + 1):\n",
    "        #     for b in range(1, n + 1):\n",
    "        #         # 判断是否符合要求\n",
    "        #         c = int(sqrt(a ** 2 + b ** 2 + 1))\n",
    "        #         if c <= n and c ** 2 == a ** 2 + b ** 2:\n",
    "        #             res += 1\n",
    "        # return res\n",
    "\n",
    "\n",
    "        # 左、右双指针\n",
    "        ans = set()\n",
    "        for i in range(1, n+1):\n",
    "            left = 1\n",
    "            right = i-1\n",
    "            while left < right:\n",
    "                s = left**2+right**2\n",
    "                if s > i**2:\n",
    "                    right -= 1\n",
    "                elif s < i**2:\n",
    "                    left += 1\n",
    "                else:\n",
    "                    ans.add((left, right, i))\n",
    "                    ans.add((right, left, i))\n",
    "                    left += 1\n",
    "\n",
    "        return len(ans)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriples(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        li = [pow(i, 2) for i in range(1, n + 1)]\n",
    "        for i in range(4, n):\n",
    "            for x in range(2, i):\n",
    "                if li[x] * 2 > li[i]:\n",
    "                    break\n",
    "                if li[i] - li[x] in li:\n",
    "                    ans += 2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def countTriples(self, n: int) -> int:\r\n",
    "        ans = 0\r\n",
    "        for a in range(1, n + 1):\r\n",
    "            for b in range(a, n + 1):\r\n",
    "                total = a**2 + b**2\r\n",
    "                c = int((total + 1) ** 0.5)\r\n",
    "                if c <= n and c**2 == total:\r\n",
    "                    ans += 2\r\n",
    "\r\n",
    "        return ans\r\n",
    "\r\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
